package com.xxwy.sort.nlogn;

import com.xxwy.sort.Sort;
import com.xxwy.sort.SortHelper;

/**
 * @author xxwy
 */
public class QuickSort2 implements Sort {
    @Override
    public void sort(int[] array, int n) {
        quickSort2(array, 0, n - 1);
    }

    private void quickSort2(int[] array, int l, int r) {
        if (l >= r) {
            return;
        }
        int partition = partition2(array, l, r);
        quickSort2(array, l, partition - 1);
        quickSort2(array, partition + 1, r);
    }

    private int partition2(int[] array, int l, int r) {
        int e = array[l];
        //arr[l+1...i-1) <=0
        //arr(j...r]>=0
        int i = l + 1, j = r;
        while (true) {
            while (i <= r && array[i] < e) {
                i++;
            }
            while (j >= l + 1 && array[j] > e) {
                j--;
            }
            if (i > j) {
                break;
            }
            SortHelper.swap(array, i, j);
            i++;
            j--;
        }
        SortHelper.swap(array, l, j);
        return j;
    }
}
